package offerbook;

/**
 * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 * <p>
 * 数组中某些数字是重复的，但不知道有几个数字是重复的。
 * <p>
 * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 * <p>
 * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
 * <p>
 * 方式1：排序，时间O(nlogn)
 * <p>
 * 方式2：Hash，时空都是O(n)
 * <p>
 * 方式3：桶，也是hash思想，时空都是O(n)
 * <p>
 * 方式4: 具体见下面解析
 * <p>
 * 方式5：标记法
 * 类似题目见笔记，寻找重复或不重复或缺失的数字
 *
 * @date 2019/11/9 0009 下午 5:46
 */
public class Code51_FindRepeatNumInArray {

    /*
     * 利用hashMap或set，略
     * 利用桶排
     */
    public boolean duplicate2(int numbers[], int length, int[] duplication) {
        if (!isLegal(numbers, length)) {
            return false;
        }
        // 0 -length-1,下标代表数，具体的值代表数个数
        int[] bucket = new int[length];
        int index;
        for (int i = 0; i < length; i++) {
            index = numbers[i];
            //已经存在数了
            if (bucket[index] >= 1) {
                duplication[0] = index;
                return true;
            }
            //否则计数+1
            bucket[index]++;
        }
        return false;
    }

    /**
     * 方式4：
     * 从1开始遍历数组 ，假设遍历到第i位置的值是m，把i位置和m位置的数交换，让m对应上其下标。
     * 当发现第i位置上的m 和第m位置上的数相等，则代表找到了，否则继续找。
     * 具体例子见剑指offer
     */
    public boolean duplicate3(int numbers[], int length, int[] duplication) {
        if (!isLegal(numbers, length)) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            //当前位置arr[i]!=i,则一直交换，把arr[i]=index与arr[index]交换，
            //直到arr[i]==i,如果index == arr[index],则说明重复
            while (numbers[i] != i) {
                int index = numbers[i];
                if (index == numbers[index]) {
                    duplication[0] = index;
                    return true;
                }
                //否则交换
                swap(numbers, index, i);
            }
        }
        return false;
    }

    public boolean mark(int numbers[], int length, int[] duplication) {
        if (!isLegal(numbers, length)) {
            return false;
        }
        for (int i = 0; i < numbers.length; i++) {
            int index = Math.abs(numbers[i]);
            if(numbers[index] < 0) {
                duplication[0] = index;
                return true;
            }
            numbers[index] = -numbers[index];
        }
        //数组的索引是0-n，把1-n归位
        for (int i = 1; i < numbers.length; i++) {
            int index = Math.abs(numbers[i]);
            if(numbers[index] < 0) {
                duplication[0] = index;
                return true;
            }
            numbers[index] = -numbers[index];
        }
         //判断0索引
        int index = numbers[0];
        //index is the repeat num
        if(numbers[index] <0) return true;
        return false;
    }
    //TODO 还原

    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    private static boolean isLegal(int[] arr, int len) {
        if (arr == null || len <= 1) {
            return false;
        }
        for (int i = 0; i < len; i++) {
            if (arr[i] < 0 || arr[i] >= len) {
                return false;
            }
        }
        return true;
    }
}
